# 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
#
#  按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
#
#
#  "123"
#  "132"
#  "213"
#  "231"
#  "312"
#  "321"
#
#
#  给定 n 和 k，返回第 k 个排列。
#
#  说明：
#
#
#  给定 n 的范围是 [1, 9]。
#  给定 k 的范围是[1, n!]。
#
#
#  示例 1:
#
#  输入: n = 3, k = 3
# 输出: "213"
#
#
#  示例 2:
#
#  输入: n = 4, k = 9
# 输出: "2314"
#
#  Related Topics 数学 回溯算法
#  👍 367 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        nums = [i + 1 for i in range(0, n)]

        fac = [1 for i in range(0, n)]
        fac[0] = 1
        for j in range(1, n):
            fac[j] = j * fac[j - 1]

        res = ""

        k -= 1
        for j in range(0, n):
            idx = int(k / fac[j])
            res += str(nums[idx])
            nums.pop(idx)

        return res
    # leetcode submit region end(Prohibit modification and deletion)
